package com.huangyi;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 串联所有单词的子串
        Solution solution1 = new Solution();
        System.out.println("串联所有单词的子串:");
        String s1 = "barfoothefoobarman";
        String[] words1 = {"foo", "bar"};
        System.out.println("s=\"barfoothefoobarman\", words=[\"foo\",\"bar\"]");
        System.out.println("结果: " + solution1.findSubstring(s1, words1)); // [0,9]

        // 测试用例 - 最小覆盖子串
        Solution2 solution2 = new Solution2();
        System.out.println("\n最小覆盖子串:");
        System.out.println("s=\"ADOBECODEBANC\", t=\"ABC\"");
        System.out.println("结果: " + solution2.minWindow("ADOBECODEBANC", "ABC")); // "BANC"
    }

    // 串联所有单词的子串
    static class Solution {
        public List<Integer> findSubstring(String s, String[] pp) {
            List<Integer> ret = new ArrayList<Integer>();
            Map<String, Integer> hash1 = new HashMap<String, Integer>();
            for (String p : pp) {
                hash1.put(p, hash1.getOrDefault(p, 0) + 1);
            }
            int len = pp[0].length(), m = pp.length;
            for (int i = 0; i < len; i++) {
                Map<String, Integer> hash2 = new HashMap<String, Integer>();
                // left 和 right 是在 s 上操作的
                for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                    String in = s.substring(right, right + len);
                    hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                    if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                        count++;
                    }
                    if (right - left + 1 > len * m) {
                        String out = s.substring(left, left + len);
                        if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                            count--;
                        }
                        hash2.put(out, hash2.get(out) - 1);
                        left += len;
                    }
                    if (count == m) {
                        ret.add(left);
                    }
                }
            }
            return ret;
        }
    }

    // 最小覆盖子串
    static class Solution2 {
        public String minWindow(String ss, String tt) {
            char[] s = ss.toCharArray();
            char[] t = tt.toCharArray();
            int[] hash1 = new int[128];
            int kinds = 0;
            for (char ch : t) {
                if (hash1[ch]++ == 0) {
                    kinds++;
                }
            }
            int[] hash2 = new int[128];
            int min_len = Integer.MAX_VALUE, begin = -1;
            for (int left = 0, right = 0, count = 0; right < s.length; right++) {
                if (++hash2[s[right]] == hash1[s[right]]) {
                    count++;
                }
                while (count == kinds) {
                    // 更新结果
                    if (right - left + 1 < min_len) {
                        min_len = right - left + 1;
                        begin = left;
                    }

                    if (hash2[s[left]]-- == hash1[s[left]]) {
                        count--;
                    }
                    left++;
                }
            }
            if (begin == -1) {
                return new String();
            }
            return ss.substring(begin, begin + min_len);
        }
    }
}